package com.atguigu.tree;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author shkstart
 * @create 2021-08-17 12:06
 */
//完全二叉树的叶子节点数(n+1)/2
    //非叶子节点的序号也是n/2-1
    //堆排序所用时间：小于一秒
public class HeapSort {
    public static void main(String[] args) {

        int[] arr={4, 6, 8, 5, 9,-5,55,59,7};
//          adjustHeap(arr,0,arr.length);
//                System.out.println(Arrays.toString(arr));//[9, 6, 8, 5, 4]
        //分步完成
//		adjustHeap(arr, 1, arr.length);
//		System.out.println("第一次" + Arrays.toString(arr)); // 4, 9, 8, 5, 6
//
//		adjustHeap(arr, 0, arr.length);
//		System.out.println("第2次" + Arrays.toString(arr)); // 9,6,8,5,4
//        System.out.println(Arrays.toString(arr));//[9, 6, 8, 5, 4]
//        heapSort(arr);
//        int[] arr = new int[8000000];
//        for (int i=0;i<8000000;i++){
//            arr[i]=(int)(Math.random()*80000000);
//        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format = simpleDateFormat.format(date1);
        System.out.println("排序前的时间="+format);

        heapSort(arr);
        System.out.println(Arrays.toString(arr));
        Date date2 = new Date();
//        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format2 = simpleDateFormat.format(date2);
        System.out.println("排序后的时间="+format2);

    }
    //编写一个堆排序的方法
//    public static void heapSort(int arr[]){
//        int temp=0;
//        //彻底完成一个大顶堆的构建
//        for (int i=arr.length/2-1;i>=0;i--){
//            adjustHeap(arr,i,arr.length);
//        }
//      //替换，再重铸
//        for (int i=arr.length-1;i>0;i--){
//            //最大一个与最小一个交换位置
//       temp=arr[i];
//       arr[i]=arr[0];
//       arr[0]=temp;
//       //重新构筑大顶堆
//       adjustHeap(arr,0,i);
//        }
////        System.out.println(Arrays.toString(arr));
//    }
    //堆排序
    public static void heapSort(int arr[]){
        int temp=0;
        //构建大顶堆
        for (int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        for (int i=arr.length-1;i>0;i--){
            //顶元素与末尾元素交换
            temp=arr[i];
            arr[i]=arr[0];
            arr[0]=temp;
            //调整堆，使之成为大顶堆
            adjustHeap(arr,0,i);
        }



    }
    //构建大顶堆

    /**
     *
     * @param arr 排序的数组
     * @param left 开始的节点
     * @param length 数组的长度
     */
//    public static void adjustHeap(int[] arr,int i,int length){
//        //取出数值
//        int temp=arr[i];
//        //无限循环左节点
//        for (int k=i*2+1;k<length;k=k*2+1){
//            //如果左节点小于右节点，那就定位到右节点
//            if (k+1<length&&arr[k]<arr[k+1]){
//                k++;
//            }
//            //如果右节点大于父节点，那就右节点赋值到父节点
//            if (arr[k]>temp){
//                arr[i]=arr[k];
//                i=k;//位移下一个
//            }else {
//                break;//这个算法是从最后一个非叶子节点开始 ，如果不用改变更改，那就不用执行了
//            }
//
//        }
//        //更改位置
//        arr[i]=temp;
//
//    }
    //如何调整堆，使得成为一个大顶堆
    public static void adjustHeap(int[] arr,int left,int length){
        int temp=arr[left];
        for (int k=left*2+1;k<length;k=k*2+1){
            if (k+1<length&&arr[k]<arr[k+1]){
                k++;
            }

            if (arr[k]>temp){
                arr[left]=arr[k];
                left=k;
            }else {
                break;
            }
        }
        arr[left]=temp;

    }
//    public  static void adjustHeap(int arr[], int i, int lenght) {
//
//        int temp = arr[i];//先取出当前元素的值，保存在临时变量
//        //开始调整
//        //说明
//        //1. k = i * 2 + 1 k 是 i结点的左子结点
//        for(int k = i * 2 + 1; k < lenght; k = k * 2 + 1) {
//            if(k+1 < lenght && arr[k] < arr[k+1]) { //说明左子结点的值小于右子结点的值
//                k++; // k 指向右子结点
//            }
//            if(arr[k] > temp) { //如果子结点大于父结点
//                arr[i] = arr[k]; //把较大的值赋给当前结点
//                i = k; //!!! i 指向 k,继续循环比较
//            } else {
//                break;//!
//            }
//        }
//        //当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部)
//        arr[i] = temp;//将temp值放到调整后的位置
//    }
}
